Network devices, such as switches and routers, are designed to forward network traffic, in the form of packets, at high line rates. One of the most important considerations for handling network traffic is packet throughput. To accomplish this, special-purpose processors known as network processors have been developed to efficiently process very large numbers of packets per second. In order to process a packet, the network processor (and/or network equipment employing the network processor) needs to extract data from the packet header indicating the destination of the packet, class of service, etc., store the payload data in memory, perform packet classification and queuing operations, determine the next hop for the packet, select an appropriate network port via which to forward the packet, etc. These operations are generally referred to as “packet processing” operations.
Traditional routers, which are commonly referred to as Layer 3 Switches, perform two major tasks in forwarding a packet: looking up the packet's destination address in the route database (also referred to a the a route or forwarding table), and switching the packet from an incoming link to one of the routers outgoing links. With recent advances in lookup algorithm and improved network processors, it appears that layer 3 switches should be able to keep up with increasing line rate speeds, such as OC-192 or higher.
Increasingly, however, users are demanding, and some vendors are providing a more discriminating form of router forwarding. This new vision of forwarding is called Layer 4 Forwarding because routing decisions can be based on headers available at Layer 4 or higher in the OSI architecture. Layer 4 forwarding is performed by packet classification routers (also referred to as Layer 4 Switches), which support “service differentiation.” This enables the router to provide enhanced functionality, such as blocking traffic from a malicious site, reserving bandwidth for traffic between company sites, and provide preferential treatment to one kind of traffic (e.g., online database transactions) over other kinds of traffic (e.g., Web browsing). In contrast, traditional routers do not provide service differentiation because they treat all traffic going to a particular address in the same way.
In packet classification routers, the route and resources allocated to a packet are determined by the destination address as well as other header fields of the packet such as the source address and TCP/UDP port numbers. Layer 4 switching unifies the forwarding functions required by firewalls, resource reservations, QoS routing, unicast routing, and multicast routing into a single unified framework. In this framework, forwarding database of a router consists of a potentially large number of filters on key header fields. A given packet header can match multiple filters; accordingly, each filter is given a cost, and the packet is forwarded using the least cost matching filter.
Traditionally, the rules for classifying a message are called filters (or rules in firewall terminology), and the packet classification problem is to determine the lowest cost matching filter or rule for each incoming message at the router. The relevant information is contained in K distinct header fields in each message (packet). For instance, the relevant fields for an IPv4 packet could comprise the Destination Address (32 bits), the Source Address (32 bits), the Protocol Field (8 bits), the Destination Port (16 bits), the Source Port (16 bits), and, optionally, the TCP flags (8 bits). Since the number of flags is limited, the protocol and flags may be combined into one field in some implementations.
The filter database of a Layer 4 Switch consists of a finite set of filters, filt1, filt2 . . . filtN. Each filter is a combination of K values, one for each header field. Each field in a filter is allowed three kinds of matches: exact match, prefix match, or range match. In an exact match, the header field of the packet should exactly match the filter field. In a prefix match, the filter field should be a prefix of the header field. In a range match, the header values should like in the range specified by the filter. Each filter filti has an associated directive dispi, which specifies how to forward a packet matching the filter.
Since header processing for a packet may match multiple filters in the database, a cost is associated with each filter to determine the appropriate (best) filter to use in such cases. Accordingly, each filter F is associated with a cost(F), and the goal is to find the filter with the least cost matching the packet's header.